1. Field of the Invention
The present invention relates to a processing device for optimizing or locally optimizing the shape of a network such as a road network, a gas network, a watersupply network, a power supply network, a telephony network, a computer network, etc.
b 2. Description of the Related Art
A Steiner problem being one of optimization problems is known as a problem of obtaining a connected tree which includes a plurality of points in a metric space as nodes and whose total distance is the shortest. A tree in a metric space is a network having no closed path. A network such as a road network, a gas network, a watersupply network, a power supply network, a telephony network, a computer network, etc. can be represented by using a tree. In the operations for installing, arranging, and wiring a target having any of these network shapes on a plane, a sphere, or in a three-dimensional space, it is vital to obtain a tree whose total distance is shorter.
For the Steiner problem, the total distance of a tree is used as a cost value, and a tree whose cost value is a minimum or a local minimum is searched. By changing the sign of a cost value, the problem of obtaining the minimum or the local minimum can be replaced with a problem of obtaining a maximum or a local maximum.
Conventionally, attempts were made mainly for a Steiner problem in a two-dimensional Euclidean space or rectilinear space, and no algorithm for solving a Steiner problem in a general metric space or a Riemann space is known. For a Steiner problem on a plane, many algorithms for obtaining the shortest distance network have been developed.
However, the conventional algorithms have the following practical problems.
(A) Cannot be applied to problems in spaces other than on a plane, such as a global network on a worldwide level, a network in a three-dimensional space, and the like.
(B) Cannot prohibit network installation in particular areas. For example, areas where a network cannot be installed or is difficult to be installed, such as a steep mountainous district, lake, sea, a nature conservation area, or a danger zone, etc. from a technical or institutional viewpoint.
(C) Since network installation costs which are respectively required for urban and rural districts per unit length are different, they cannot be estimated based only on the lengths of networks. Accordingly, a network installation cost cannot be accurately optimized.
As described above, the problems inherent in the conventional algorithms exist in a point that the algorithms can be applied only to the case where the length of a network is given as a Euclidean distance on a plane.
An object of the present invention is to provide a processing device with higher universality, which comprises an algorithm for searching for a suitable network shape in a general metric space.
A processing device according to the present invention comprises a generating unit, a storing unit, a reshaping unit, and an outputting unit. The generating unit generates a tree model in an arbitrary space. The storing unit stores the data of existing nodes included in the tree model. The reshaping unit reshapes the tree model based on the existing nodes. The outputting unit outputs a reshape result.